/*
https://leetcode-cn.com/problems/rectangle-area-ii/solution/ju-xing-mian-ji-ii-by-leetcode/
 */
import java.util.*;

public class Solution850 {

    static class Segment{
        int start;
        int end;
        int count;
        int total;
        Segment left;
        Segment right;
        Integer[] f;

        public Segment(int left,int right,Integer[] x){
            start=left;
            end=right;
            f=x;
        }

        public void update(int l,int r,int val){
            if (r<start || l>end){
                return;
            }
            if (start>=l && end<=r && left==null) {
                if (count == 0) {
                    total = f[end + 1] - f[start];
                }
                count += val;
                if (count == 0) {
                    total = 0;
                }
                return;
            }
            if (left==null){
                left=new Segment(start,(start+end)/2,f);
                left.count=count;
                if (left.count>0){
                    left.total=f[left.end+1]-f[left.start];
                }
            }
            if (right==null){
                right=new Segment((start+end)/2+1,end,f);
                right.count=count;
                if (right.count>0){
                    right.total=f[right.end+1]-f[right.start];
                }
            }
            left.update(l,r,val);
            right.update(l,r,val);
            total=left.total+ right.total;
        }
    }

    public int rectangleArea(int[][] rectangles) {
        int mod=1000000007;
        List<int[]> list=new ArrayList<>();
        Set<Integer> set=new HashSet<>();
        for (int[] rectangle : rectangles) {
            list.add(new int[]{0,rectangle[1],rectangle[0],rectangle[2]});
            list.add(new int[]{1,rectangle[3],rectangle[0],rectangle[2]});
            set.add(rectangle[0]);
            set.add(rectangle[2]);
        }
        list.sort(Comparator.comparingInt(a -> a[1]));
        Integer[] target= new Integer[set.size()];
        int v=0;
        for (Integer integer : set) {
            target[v]=integer;
            v++;
        }
        Arrays.sort(target);
        int id=0;
        Map<Integer,Integer> map=new HashMap<>();
        for (Integer integer : target) {
            map.put(integer,id);
            id++;
        }
        Segment segment=new Segment(0,id-2,target);
        int cur=list.get(0)[1];
        long ans=0;
        for (int[] ints : list) {
            ans=(ans+(long)segment.total*(ints[1]-cur)%mod)%mod;
            cur=ints[1];
            int pos=ints[0]==0?1:-1;
            segment.update(map.get(ints[2]),map.get(ints[3])-1,pos);
        }
        return (int)ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution850().rectangleArea(new int[][]{{49,40,62,100},{11,83,31,99},{19,39,30,99}}));
    }
}
